{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Largest BST in a Binary Tree\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/aZX6PIoVv0gSHXHeIAA9eA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "You are given the root of a binary tree. Find and return the largest subtree of that tree, which is a valid binary search tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    ''' Class Definition '''\n",
    "    \n",
    "    def __init__(self, key):\n",
    "        ''' The Constructor'''\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.key = key\n",
    "    \n",
    "    def __str__(self):\n",
    "        ''' Preorder Traversal '''\n",
    "        answer = str(self.key)\n",
    "        if self.left:\n",
    "            answer += str(self.left)\n",
    "        if self.right:\n",
    "            answer += str(self.right)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def largest_bst_subtree(root: TreeNode) -> dict:\n",
    "    if root is None:\n",
    "        return {\n",
    "            'size': 0,\n",
    "            'root': None,\n",
    "            'min': float('Inf'),\n",
    "            'max': -float('Inf')\n",
    "        }\n",
    "    left_info = largest_bst_subtree(root.left)\n",
    "    right_info = largest_bst_subtree(root.right)\n",
    "    size_include_itself = 0\n",
    "    if (left_info['root'] == root.left and\n",
    "        right_info['root'] == root.right and\n",
    "        root.key > left_info['max'] and\n",
    "        root.key < right_info['min']):\n",
    "        size_include_itself = left_info['size'] + right_info['size'] + 1\n",
    "    max_size = max(left_info['size'], right_info['size'], size_include_itself)\n",
    "    if left_info['size'] > right_info['size']:\n",
    "        max_root = left_info['root']\n",
    "    else:\n",
    "        max_root = right_info['root']\n",
    "    if max_size == size_include_itself:\n",
    "        max_root = root\n",
    "    return {\n",
    "        'size': max_size,\n",
    "        'root': max_root,\n",
    "        'min': min(left_info['min'], right_info['min'], root.key),\n",
    "        'max': max(left_info['max'], right_info['max'], root.key)\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "749\n"
     ]
    }
   ],
   "source": [
    "#     5\n",
    "#    / \\\n",
    "#   6   7\n",
    "#  /   / \\\n",
    "# 2   4   9\n",
    "node = TreeNode(5)\n",
    "node.left = TreeNode(6)\n",
    "node.right = TreeNode(7)\n",
    "node.left.left = TreeNode(2)\n",
    "node.right.left = TreeNode(4)\n",
    "node.right.right = TreeNode(9)\n",
    "print(largest_bst_subtree(node)['root'])\n",
    "#749"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
